package leetcode.array;

/**
 * @author Cheng Jun
 * Description: 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
 * <p>
 * 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
 * https://leetcode.cn/problems/first-missing-positive/
 * @version 1.0
 * @date 2022/7/22 19:37
 * 面试题 二刷 困难题
 */
public class firstMissingPositive {

    public static void main(String[] args) {

    }
    // 用hashset，很容易就解决了这个问题，但是不满足题目的空间复杂度要求
    // hashset的底层也是数组，那我们 应该想想如何 利用 nums自身数组，进行 原地hash
    static int firstMissingPositive(int[] nums) {
        // [1,2,0] 3
        // [7,8,9,11,12] 1
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            // nums[i] != nums[nums[i] - 1] 表示当前下标的数值和要交换位置的数值 不一致才进行交换，不然会出现死循环
            while (0 < nums[i] && nums[i] <= length && nums[i] != nums[nums[i] - 1]) {
                swap(nums, nums[i] - 1, i);
            }
        }
        // 如果当前下标上的数字 不等于 下标加1，则（i+1）是没有出现的最小的正整数
        for (int i = 0; i < length; i++) {
            if (nums[i] != (i + 1)) {
                return i + 1;
            }
        }
        return length + 1;
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
